CAP 定理

When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.

In this note, we have shown that it is impossible to reliably provide atomic, consistent data when there are partitions in the network. It is feasible, however, to achieve any two of the three properties: consistency, availability, and partition tolerance. In an asynchronous model, when no clocks are available, the impossibility result is fairly strong: it is impossible to provide consistent data, even allowing stale data to be returned when messages are lost. However in partially synchronous models it is possible to achieve a practical compromise between consistency and availability. In particular, most real-world systems today are forced to settle with returning “most of the data, most of the time.” Formalizing this idea and studying algorithms for achieving it is an interesting subject for future theoretical research.

一貫性 (consistency)

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. One important property of an atomic read/write shared memory is that any read operation that begins after a write operation completes must return that value, or the result of a later write operation.

可用性 (availability)

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. That is, any algorithm used by the service must eventually terminate. In some ways this is a weak definition of availability: it puts no bound on how long the algorithm may run before terminating, and therefore allows unbounded computation. On the other hand, when qualified by the need for partition tolerance, this can be seen as a strong definition of availability: even when severe network failures occur, every request must terminate.

分斷耐性 (partition-tolerance)

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost.)

Theorem 1

It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

Availability

Atomic consistency

in all fair executions (including those in which messages are lost).

Corollary 1.1

It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

Availability, in all fair executions,

Atomic consistency, in fair executions in which no messages are lost.

Theorem 2

It is impossible in the partially synchronous network model to implement a read/write data object that guarantees the following properties:

Availability

Atomic consistency

in all executions (even those in which messages are lost).

Definition 3

A timed execution, α, of a read-write object is Delayed-t Consistent if:

1. P is a partial order that orders all write operations, and orders all read operations with respect to the write operations.

2. The value returned by every read operation is exactly the one written by the previous write operation in P (or the initial value, if there is no such previous write in P).

3. The order in P is consistent with the order of read and write requests submitted at each node.

4. (Atomicity) If all messages in the execution are delivered, and an operation θ completes before an operation φ begins, then φ does not precede θ in the partial order P,

5. (Weakly Consistent) Assume there exists an interval of time longer than t in which no messages are lost. Further, assume an operation, θ, completes before the interval begins, and another operation, φ, begins after the interval ends. Then φ does not precede θ in the partial order P.

Theorem 4

The modified centralized algorithm is Delayed-t consistent.

BASE←→ACID

BASE

basically available

soft-state

結果整合性 (eventually consistent)

ACID

原子性 (atomicity)

一貫性 (consistemcy)

獨立性 (isolation)

永續性 (durability)

SALT

decentralized databases での一貫性 model

transactional context

逐次的 (sequential)

Transactions occur in some sequential ordering… though that may be determined by the winning miner in some blockchains.

合意された (agreed)

There is a consensus on what is to transpire to produce a common state… which may require a leader election or a winner such as in Proof of Work systems.

導かれた (ledgered)

All evidence of transactions are maintained in a historical ledger of events… which allows the current state to be verified as correct.

改竄されない (tamper-resistant)

A significant plurality is required to alter committed transactions… often called immutability but that’s a misnomer.

systemic context

對稱的 (symmetric)

Every node is empowered to validate their data (I modified this a bit from their paper because they assume public consensus networks but this can be abstracted to private chains that do not have symmetric responsibility of nodes).

管理者なし (admin-free)

I prefer the term ‘autonomous’, but it means there’s a self-governance to the system and no one node can change the system on its own.

導かれた (ledgered)

All peers maintain a ledgered system of the data and have rules for negotiating the addition of blocks onto the ledger.

時閒的に合意された (time-consensual)

There is a defined expectation of approximate block creation times.

network 上の name service は以下の三つの性質を全ては滿たせない

human-meaningful

Meaningful and memorable (low-entropy) names are provided to the users.

secure

The amount of damage a malicious entity can inflict on the system should be as low as possible.

decentralized

Names correctly resolve to their respective entities without the use of a central authority or service.